Search Results

Documents authored by Marques-Silva, João

Found 2 Possible Name Variants:

Marques-Silva, Joao

Document
DOI: 10.4230/DagRep.11.8.1
Extending the Synergies Between SAT and Description Logics (Dagstuhl Seminar 21361)

Authors: Joao Marques-Silva, Rafael Peñaloza, and Uli Sattler

Published in: Dagstuhl Reports, Volume 11, Issue 8 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21361 "Extending the Synergies Between SAT and Description Logics". Propositional satisfiability (SAT) and description logics (DL) are two successful areas of computational logic where automated reasoning plays a fundamental role. While they share a common core (formalised on logic), the developments in both areas have diverged in their scopes, methods, and applications. The goal of this seminar was to reconnect the SAT and DL communities (understood in a broad sense) so that they can benefit from each other. The seminar thus focused on explaining the foundational principles, main results, and open problems of each area, and discussing potential avenues for collaborative progress.
Cite as

Joao Marques-Silva, Rafael Peñaloza, and Uli Sattler. Extending the Synergies Between SAT and Description Logics (Dagstuhl Seminar 21361). In Dagstuhl Reports, Volume 11, Issue 8, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{marquessilva_et_al:DagRep.11.8.1,
  author =	{Marques-Silva, Joao and Pe\~{n}aloza, Rafael and Sattler, Uli},
  title =	{{Extending the Synergies Between SAT and Description Logics (Dagstuhl Seminar 21361)}},
  pages =	{1--10},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{8},
  editor =	{Marques-Silva, Joao and Pe\~{n}aloza, Rafael and Sattler, Uli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.8.1},
  URN =		{urn:nbn:de:0030-drops-157661},
  doi =		{10.4230/DagRep.11.8.1},
  annote =	{Keywords: description logics, propositional satisfiability, reasoning services, standard and non-standard inferences}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.21
On the Tractability of Explaining Decisions of Classifiers

Authors: Martin C. Cooper and João Marques-Silva

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Explaining decisions is at the heart of explainable AI. We investigate the computational complexity of providing a formally-correct and minimal explanation of a decision taken by a classifier. In the case of threshold (i.e. score-based) classifiers, we show that a complexity dichotomy follows from the complexity dichotomy for languages of cost functions. In particular, submodular classifiers allow tractable explanation of positive decisions, but not negative decisions (assuming P≠NP). This is an example of the possible asymmetry between the complexity of explaining positive and negative decisions of a particular classifier. Nevertheless, there are large families of classifiers for which explaining both positive and negative decisions is tractable, such as monotone or linear classifiers. We extend tractable cases to constrained classifiers (when there are constraints on the possible input vectors) and to the search for contrastive rather than abductive explanations. Indeed, we show that tractable classes coincide for abductive and contrastive explanations in the constrained or unconstrained settings.
Cite as

Martin C. Cooper and João Marques-Silva. On the Tractability of Explaining Decisions of Classifiers. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.CP.2021.21,
  author =	{Cooper, Martin C. and Marques-Silva, Jo\~{a}o},
  title =	{{On the Tractability of Explaining Decisions of Classifiers}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.21},
  URN =		{urn:nbn:de:0030-drops-153125},
  doi =		{10.4230/LIPIcs.CP.2021.21},
  annote =	{Keywords: machine learning, tractability, explanations, weighted constraint satisfaction}
}

Marques-Silva, João

Document
DOI: 10.4230/DagRep.11.8.1
Extending the Synergies Between SAT and Description Logics (Dagstuhl Seminar 21361)

Authors: Joao Marques-Silva, Rafael Peñaloza, and Uli Sattler

Published in: Dagstuhl Reports, Volume 11, Issue 8 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21361 "Extending the Synergies Between SAT and Description Logics". Propositional satisfiability (SAT) and description logics (DL) are two successful areas of computational logic where automated reasoning plays a fundamental role. While they share a common core (formalised on logic), the developments in both areas have diverged in their scopes, methods, and applications. The goal of this seminar was to reconnect the SAT and DL communities (understood in a broad sense) so that they can benefit from each other. The seminar thus focused on explaining the foundational principles, main results, and open problems of each area, and discussing potential avenues for collaborative progress.
Cite as

Joao Marques-Silva, Rafael Peñaloza, and Uli Sattler. Extending the Synergies Between SAT and Description Logics (Dagstuhl Seminar 21361). In Dagstuhl Reports, Volume 11, Issue 8, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{marquessilva_et_al:DagRep.11.8.1,
  author =	{Marques-Silva, Joao and Pe\~{n}aloza, Rafael and Sattler, Uli},
  title =	{{Extending the Synergies Between SAT and Description Logics (Dagstuhl Seminar 21361)}},
  pages =	{1--10},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{8},
  editor =	{Marques-Silva, Joao and Pe\~{n}aloza, Rafael and Sattler, Uli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.8.1},
  URN =		{urn:nbn:de:0030-drops-157661},
  doi =		{10.4230/DagRep.11.8.1},
  annote =	{Keywords: description logics, propositional satisfiability, reasoning services, standard and non-standard inferences}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.21
On the Tractability of Explaining Decisions of Classifiers

Authors: Martin C. Cooper and João Marques-Silva

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Explaining decisions is at the heart of explainable AI. We investigate the computational complexity of providing a formally-correct and minimal explanation of a decision taken by a classifier. In the case of threshold (i.e. score-based) classifiers, we show that a complexity dichotomy follows from the complexity dichotomy for languages of cost functions. In particular, submodular classifiers allow tractable explanation of positive decisions, but not negative decisions (assuming P≠NP). This is an example of the possible asymmetry between the complexity of explaining positive and negative decisions of a particular classifier. Nevertheless, there are large families of classifiers for which explaining both positive and negative decisions is tractable, such as monotone or linear classifiers. We extend tractable cases to constrained classifiers (when there are constraints on the possible input vectors) and to the search for contrastive rather than abductive explanations. Indeed, we show that tractable classes coincide for abductive and contrastive explanations in the constrained or unconstrained settings.
Cite as

Martin C. Cooper and João Marques-Silva. On the Tractability of Explaining Decisions of Classifiers. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.CP.2021.21,
  author =	{Cooper, Martin C. and Marques-Silva, Jo\~{a}o},
  title =	{{On the Tractability of Explaining Decisions of Classifiers}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.21},
  URN =		{urn:nbn:de:0030-drops-153125},
  doi =		{10.4230/LIPIcs.CP.2021.21},
  annote =	{Keywords: machine learning, tractability, explanations, weighted constraint satisfaction}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact